package com.demo.interview;

import cn.hutool.core.util.RandomUtil;

import java.util.HashMap;
import java.util.Map;

import static java.lang.Math.min;

/**
 * 乌鸫科技算法面试题
 * 标题：字符串变换|时间限制：1秒|内存限制：131071K|语言限制：不限
 * [字符串变换]小强拥有一种神奇的魔法：对于一个字符串，它能在花费1的代价下，把任何位置的任何字符移动到字符串末端。
 * 现在给定两个长度相同的小写字符串S和T，请你计算出小强至少需要多少次魔法将S变成T？
 * 输入描述：
 * 第一行包含一个字符串S
 * 第二行包含一个字符串T
 * 1<=|S|=|T|<=100000
 * 其中对于S和T都只包含小写字母
 * <p>
 * 输出描述：
 * 一行一个数字表示答案，如果不能从S变成T，则输出-1.
 * <p>
 * 示例1：
 * 输入：
 * acdk
 * ckad
 * 输出：
 * 2
 * 示例2：
 * 输入：
 * cdak
 * ckad
 * 输出：
 * 2
 *
 * @author shenguangyang
 */
public class WuDong_StringChange {
    public static int minDistance(String s, String t) {
        Map<Integer, Integer> data = new HashMap<>();
        int sPtr = 0;
        int tPtr = 0;
        int count = 0;
        int length = s.length();
        int pollCount = 0;
        for (;;) {
            if (sPtr <= (length - 1) && tPtr <= (length - 1)) {
                char s1 = s.charAt(sPtr);
                char t1 = t.charAt(tPtr);
                if (s1 != t1) {
                    Integer charCount = data.get((int)s1);
                    data.put((int)s1, charCount == null ? 1 : charCount + 1);
                    pollCount++;
                } else {
                    tPtr++;
                }
                sPtr++;
            } else if (sPtr >= (length - 1) && pollCount > 0) {
                char t1 = t.charAt(tPtr);
                Integer charCount = data.get((int)t1);
                if (charCount == null || charCount <= 0) {
                    return -1;
                }
                count++;
                tPtr++;
                pollCount--;
                data.put((int)t1, charCount - 1);
            } else {
                break;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String s = RandomUtil.randomString(100000);
        StringBuilder t = new StringBuilder("");
        int length = s.length();
        for (int i = 0; i < s.length(); i++) {
            t.append(s.charAt(length - i - 1));
        }

        System.out.println(minDistance("acdk", "ckad")); // 2
        System.out.println(minDistance("abcd", "dcba")); // 3
        System.out.println(minDistance("acdk", "czad")); // -1
        System.out.println(minDistance("acadk", "cakad")); // 2
        long t1 = System.currentTimeMillis();
        System.out.println(minDistance(s, t.toString())); // 2
        System.out.println("time: " + (System.currentTimeMillis() - t1) + " ms");
    }
}
